Halin graph
In graph theory, a mathematical discipline, a Halin graph is a planar graph constructed from a plane embedding of a tree with at least four vertices and with no vertices of degree 2, by connecting all the leaves of the tree (the vertices of degree 1) with a cycle that passes around the tree in the natural cyclic order defined by the embedding of the tree.[1] Halin graphs are named after German mathematician Rudolf Halin, who defined them in 1964;[2] they are sometimes also called roofless polyhedra.[3]
Examples
Every wheel graph (the graph of a pyramid) is a Halin graph, whose tree is a star. The graph of a triangular prism is also a Halin graph; it can be drawn so that one of its rectangular faces is the exterior cycle, and the remaining edges form a tree with four leaves, two interior vertices, and five edges.
The Frucht graph, one of the two smallest cubic graphs with no nontrivial graph automorphisms, is also a Halin graph.
Properties
- Every Halin graph is an edge-minimal planar 3-connected graph,[1] and therefore by Steinitz's theorem it is a polyhedral graph.
- Every Halin graph has a unique planar embedding (up to the choice of the outer space; i.e., a unique embedding onto a 2-sphere).[1]
- Every Halin graph is a Hamiltonian graph, and every edge of the graph belongs to a Hamiltonian cycle. Moreover, any Halin graph remains Hamiltonian after deletion of any vertex.[3]
- Every Halin graph is almost pancyclic, in the sense that it has cycles of all lengths from 3 to n with the possible exception of a single even length. Moreover, any Halin graph remains almost pancyclic if a single edge is contracted, and every Halin graph without interior vertices of degree three is pancyclic.[4]
- Every Halin graph has treewidth at most three;[5] therefore, many graph optimization problems that are NP-complete for arbitrary planar graphs, such as finding a maximum independent set, may be solved in linear time on Halin graphs using dynamic programming.[6]
- Because every tree contains two leaves that share the same parent, every Halin graph contains a triangle. In particular, it is not possible for a Halin graph to be a triangle-free graph nor a bipartite graph.
- The weak dual of a Halin graph (the graph whose vertices correspond to bounded faces of the Halin graph, and whose edges correspond to adjacent faces) is biconnected and outerplanar. A planar graph is a Halin graph if and only if its weak dual is biconnected and outerplanar.[7]
References
- ^ a b c Encyclopaedia of Mathematics, first Supplementary volume, 1988, ISBN 0792347099, p. 281, article "Halin Graph", and references therein.
- ^ Halin, R. (1964), "Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen" (in German), Mathematische Annalen 156 (3): 216–225, doi:10.1007/BF01363288 .
- ^ a b Cornuéjols, G.; Naddef, D.; Pulleyblank, W. R. (1983), "Halin graphs and the travelling salesman problem", Mathematical Programming 26 (3): 287–294, doi:10.1007/BF02591867 .
- ^ Skowrońska, Mirosława (1985), "The pancyclicity of Halin graphs and their exterior contractions", in Alspach, Brian R.; Godsil, Christopher D., Cycles in Graphs, Annals of Discrete Mathematics, 27, Elsevier Science Publishers B.V., pp. 179–194 .
- ^ Bodlaender, Hans (1988), Planar graphs with bounded treewidth, Technical Report RUU-CS-88-14, Department of Computer Science, Utrecht University, http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1988/1988-14.pdf .
- ^ Bodlaender, Hans (1988), "Dynamic programming on graphs with bounded treewidth", Proceedings of the 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 317, Springer-Verlag, pp. 105–118 .
- ^ Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635 .
External links